package day20;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 给你一个以字符串表示的非负整数num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
 * <p>
 * <p>
 * 示例 1 ：
 * <p>
 * 输入：num = "1432219", k = 3
 * 输出："1219"
 * 解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
 * 示例 2 ：
 * <p>
 * 输入：num = "10200", k = 1
 * 输出："200"
 * 解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
 * 示例 3 ：
 * <p>
 * 输入：num = "10", k = 2
 * 输出："0"
 * 解释：从原数字移除所有的数字，剩余为空就是 0 。
 */
public class Solution2 {
    public String removeKdigits(String num, int k) {
        if (num.length() == k) {
            return "0";
        }
        char[] chars = num.toCharArray();
        Deque<Character> deque = new LinkedList<>();
        deque.offerLast(chars[0]);
        for (int i = 1; i < chars.length; i++) {
            if (!deque.isEmpty()) {
                if (chars[i] >= deque.peekLast()) {
                    deque.offerLast(chars[i]);
                } else {
                    while (!deque.isEmpty() && chars[i] < deque.peekLast()) {
                        if (k > 0) {
                            deque.pollLast();
                            k--;
                        } else {
                            break;
                        }
                    }
                    deque.offerLast(chars[i]);
                }
            } else {
                deque.offerLast(chars[i]);
            }
        }
        if (k == 0) {
            if (deque.isEmpty()) {
                return "0";
            } else {
                StringBuilder str = new StringBuilder();
                Boolean firstZro = true;
                while (!deque.isEmpty()) {
                    char temp = deque.pollFirst();
                    if (firstZro && temp == '0') {
                        continue;
                    } else {
                        firstZro = false;
                        str.append(temp);
                    }
                }
                return str.toString().length() == 0 ? "0" : str.toString();
            }
        } else {
            while (k > 0 && !deque.isEmpty()) {
                deque.pollLast();
                k--;
            }
            if (deque.isEmpty()) {
                return "0";
            }

            StringBuilder str = new StringBuilder();
            Boolean sZro = true;
            while (!deque.isEmpty()) {
                char temp = deque.pollFirst();
                if (sZro && temp == '0') {
                    continue;
                } else {
                    sZro = false;
                    str.append(temp);
                }
            }
            return str.toString().length() == 0 ? "0" : str.toString();

        }
    }
}
